package campus;


import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;


/**
 * 鏍℃嫑璁粌鐨勭ず鑼冪偣 Created by lecky on 2016/8/9 0009.
 */
public class BTree {
	class TreeNode {
		private int val;
		private TreeNode left;
		private TreeNode right;

		public TreeNode(int val) {
			this.val = val;
		}
	}

	/**
	 * 鍏堝簭閬嶅巻锛岄�掑綊�1�7�炵幄1�7
	 */
	public List<Integer> pre_order(TreeNode root) {
		List list = new ArrayList<Integer>();
		pre_order_help(root, list);
		return list;
	}

	private void pre_order_help(TreeNode root, List<Integer> list) {
		if (root != null) {
			list.add(root.val);
			pre_order_help(root.left, list);
			pre_order_help(root.right, list);
		}
	}

	/**
	 * f 鍏堝簭閬嶅巻锛屾爤�1�7�炵幇f
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> pre_order_stack(TreeNode root) {
		ArrayList<Integer> list = new ArrayList();
		if (root == null)
			return list;
		Stack<TreeNode> stack = new Stack();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			list.add(node.val);
			if (node.right != null)
				stack.push(node.right);
			if (node.left != null)
				stack.push(node.left);
		}
		return list;
	}

	/**
	 * 涓簭閬嶅巻锛岄�掑綊�1�7�炵幄1�7
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> in_order(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		in_order_help(root, list);
		return list;
	}

	private void in_order_help(TreeNode root, ArrayList<Integer> list) {
		if (root != null) {
			in_order_help(root.left, list);
			list.add(root.val);
			in_order_help(root.right, list);
		}
	}

	/**
	 * 涓簭閬嶅巻鏍堝疄鐜ￄ1�7
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> in_order_stack(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		if (root == null)
			return list;
		Stack<TreeNode> stack = new Stack<>();
		while (root != null || !stack.isEmpty()) {
			if (root != null) {
				stack.push(root);
				root = root.left;
			} else {
				root = stack.pop();
				list.add(root.val);
				root = root.right;
			}
		}
		return list;
	}

	/**
	 * 閫掑綊�1�7�炵幇鍚庡簭閬嶅巄1�7
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> post_order(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		post_order_help(root, list);
		return list;
	}

	private void post_order_help(TreeNode root, ArrayList<Integer> list) {
		if (root != null) {
			post_order_help(root.left, list);
			post_order_help(root.right, list);
			list.add(root.val);
		}
	}

	/**
	 * 判断二叉树对秄1�7
	 * 
	 * @param root
	 * @return
	 */
	public boolean isSymmetric(TreeNode root) {
		if (root == null)
			return true;
		return validate(root.left, root.right);
	}

	private boolean validate(TreeNode left, TreeNode right) {
		if (left == null && right == null)
			return true;
		if (left != null && right != null && left.val == right.val)
			return validate(left.left, right.right)
					&& validate(left.right, right.left);
		return false;
	}

	/**
	 * �ж�һ��B���Ƿ�ΪBST ����һ�� 1���������ö������� 2��������ÿһ���ڵ㣬�ж��Ƿ�����������<�ýڵ�<������ ʱ�临�Ӷ�O(N*N)
	 * 
	 * @param root
	 * @return
	 */
	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;
		if (validate(root))
			return isValidBST(root.left) && isValidBST(root.right);
		return false;
	}

	private boolean validate(TreeNode node) {
		return validateLeft(node, node.left) && validateRight(node, node.right);
	}

	private boolean validateRight(TreeNode node, TreeNode right) {
		if (right == null)
			return true;
		if (right.val <= node.val)
			return false;
		return validateRight(node, right.left)
				&& validateRight(node, right.right);
	}

	private boolean validateLeft(TreeNode node, TreeNode left) {
		if (left == null)
			return true;
		if (left.val >= node.val)
			return false;
		return validateLeft(node, left.left) && validateLeft(node, left.right);
	}

	/**
	 * �ж�һ��B���Ƿ�ΪBST�� ����BST�������ϵ�ÿһ���ڵ㶼��һ��ȡֵ��Χ�����ڵ�� ȡֵ��ΧΪ��-OO��+OO�� ʱ�临�Ӷ�ΪO(N)
	 * 
	 * @param root
	 * @return
	 */
	public boolean isValidBST2(TreeNode root) {
		return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	private boolean validate(TreeNode node, int minValue, int maxValue) {
		if (node == null)
			return true;
		if (node.val > minValue && node.val < maxValue)
			return validate(node.left, minValue, node.val)
					&& validate(node.right, node.val, maxValue);
		return false;
	}

	/**
	 * �ж�һ�Ŷ������Ƿ�Ϊƽ������� ����һ���ж�ÿһ���ڵ�Ϊ���ڵ���������Ƿ����㣬|�����-�����|<=1 1������������
	 * 2���жϸýڵ�Ϊ���ڵ�������Ƿ�����ƽ������
	 * 
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null)
			return true;
		if (validateBanlance(root))
			return isBalanced(root.left) && isBalanced(root.right);
		return false;
	}

	private boolean validateBanlance(TreeNode root) {
		if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1)
			return true;
		return false;
	}
	
	/**
	 * 104. Maximum Depth of Binary Tree
	 * @param root
	 * @return
	 */
	public int maxDepth(TreeNode root) {
		if (root == null)
			return 0;
		return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	/**
	 * 104. Maximum Depth of Binary Tree
	 * @param root
	 * @return
	 */
	private int maxDeepth=Integer.MIN_VALUE;
	public int maxDepth2(TreeNode root) {
		if(root==null)
			return 0;
		travelMax(root,1);
		return maxDeepth;
	}
	
	private void travelMax(TreeNode root, int i) {
		if(root.left==null&&root.right==null){
			maxDeepth=Math.max(maxDeepth, i);
			return;
		}
		if(root.left!=null)
			travelMax(root.left, i+1);
		if(root.right!=null)
		travelMax(root.right, i+1);
	}

	/**
	 * �����������·����
	 * 
	 * @param root
	 * @return
	 */
	private int max = Integer.MIN_VALUE;

	public int maxPathSum(TreeNode root) {
		help(root);
		return max;
	}

	/**
	 * ������rootΪ���ڵ�������ϣ���root���ڵ㵽ĳҶ�ӽڵ�����·����
	 * 
	 * @param root
	 * @return
	 */
	private int help(TreeNode root) {
		if (root == null)
			return 0;
		int left = Math.max(0, help(root.left));
		int right = Math.max(0, help(root.right));
		max = Math.max(max, left + root.val + right);
		return root.val + Math.max(left, right);
	}

	/**
	 * �ҳ����дӸ��ڵ㵽Ҷ�ӽڵ��·��
	 * 
	 * @param root
	 * @return
	 */
	public List<String> binaryTreePaths(TreeNode root) {
		List<String> list = new ArrayList<String>();
		if (root == null)
			return list;
		help(root, "", list);
		return list;
	}

	private void help(TreeNode root, String s, List<String> list) {
		if (root.left == null && root.right == null) {
			s = s + root.val;
			list.add(s);
			return;
		}
		s = s + root.val + "->";
		if (root.left != null)
			help(root.left, s, list);
		if (root.right != null)
			help(root.right, s, list);
	}

	/**
	 * �����������л��ͷ����л� ʹ����������ķ�ʽ���������л�
	 */
	public String serialize(TreeNode root) {
		StringBuilder result = new StringBuilder();
		if (root == null)
			return result.toString();
		help(root, result);
		return result.toString();
	}

	private void help(TreeNode root, StringBuilder result) {
		if (root == null) {
			result.append("#!");
			return;
		}
		result.append(root.val).append("!");
		help(root.left, result);
		help(root.right, result);
	}

	/**
	 * �������ķ����л� ������������ɵ����л����з����л�
	 * 
	 * @param str
	 * @return
	 */
	public TreeNode deserialize(String str) {
		if (str == null || "".equals(str))
			return null;
		String[] strings = str.split("!");
		Queue<String> queue = new LinkedList<String>();
		for (String s : strings)
			queue.offer(s);
		return help(queue);
	}

	private TreeNode help(Queue<String> queue) {
		String s = queue.poll();
		if ("#".equals(s))
			return null;
		TreeNode node = new TreeNode(Integer.valueOf(s));
		node.left = help(queue);
		node.right = help(queue);
		return node;
	}

	/**
	 * �ж����Ŷ������Ƿ���� 1���ṹ��ͬ 2��ֵ���
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if ((p == null && q != null) || (p != null && q == null))
			return false;
		if (p == null && q == null)
			return true;
		if (p.val != q.val)
			return false;
		return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
	}

	/**
	 * �ж����Ŷ������Ƿ���� ʹ�����л����ж� ���������������л�Ϊ�ַ���֮��Ƚ��ַ����Ƿ����
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTree2(TreeNode p, TreeNode q) {
		String first = serialize(p);
		String second = serialize(q);
		if (first.equals(second))
			return true;
		return false;
	}

	/**
	 * �ж϶�����q�Ƿ��Ƕ�����p������
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSubTree(TreeNode p, TreeNode q) {
		if (q == null)
			return true;
		if (p == null)
			return false;
		return validate2(p, q);
	}

	private boolean validate2(TreeNode p, TreeNode q) {
		if (p != null) {
			if (p.val == q.val && isSameTree(p, q))
				return true;
			validate(p.left, q);
			validate(p.right, q);
		}
		return false;
	}

	/**
	 * �ж϶�����q�Ƿ��Ƕ�����p������ �����Ŷ������������л����ж�q���ַ����Ƿ�Ϊq���ַ������Ӵ�
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSubTree2(TreeNode p, TreeNode q) {
		String first = serialize(p);
		String second = serialize(q);
		if (first.contains(second))
			return true;
		else
			return false;
	}

	/**
	 * 102. Binary Tree Level Order Traversal ���㼶�������������Ӹ��ڵ㵽Ҷ�ӽڵ�
	 * 
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> list = new ArrayList<>();
		help(root, list, 0);
		return list;
	}

	private void help(TreeNode root, List<List<Integer>> list, int level) {
		if (root == null)
			return;
		if (level >= list.size())
			list.add(new ArrayList<Integer>());
		list.get(level).add(root.val);
		help(root.left, list, level + 1);
		help(root.right, list, level + 1);
	}

	/**
	 * 107. Binary Tree Level Order Traversal II * ���㼶��������������Ҷ�ӽڵ㵽���ڵ�
	 */
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> list = new ArrayList<>();
		help2(root, list, 0);
		Collections.reverse(list);
		return list;
	}

	private void help2(TreeNode root, List<List<Integer>> list, int i) {
		if (root == null)
			return;
		if (i == list.size())
			list.add(new ArrayList<Integer>());
		help2(root.left, list, i + 1);
		help2(root.right, list, i + 1);
		list.get(i).add(root.val);
	}

	/**
	 * 111. Minimum Depth of Binary Tree
	 * 
	 * @param root
	 * @return
	 */
	private int minDeepth=Integer.MAX_VALUE;

	public int minDepth(TreeNode root) {
		if(root==null)
			return 0;
		travel(root,1);
		return minDeepth;
	}

	private void travel(TreeNode root, int i) {
		if(root.left==null&&root.right==null){
			minDeepth=Math.min(minDeepth, i);
			return;
		}
		if(root.left!=null)
			travel(root.left, i+1);
		if(root.right!=null)
			travel(root.right, i+1);
	}
	
	/**
	 * 235. Lowest Common Ancestor of a Binary Search Tree
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if(root==null)
			return null;
		if(p==null||q==null)
			return root;
		if(root.val>Math.max(p.val, q.val))
			return lowestCommonAncestor(root.left, p, q);
		if(root.val<Math.min(p.val, q.val))
			return lowestCommonAncestor(root.right, p, q);
		return root;
	}
	
	/**
	 * 236. Lowest Common Ancestor of a Binary Tree
	 * ������rootΪ���ڵ������p��q�������������
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		if(root==null || root==p ||root==q)
			return root;
		TreeNode leftNode = lowestCommonAncestor2(root.left, p, q);
		TreeNode rightNode = lowestCommonAncestor2(root.right, p, q);
		if(leftNode!=null&&rightNode!=null)
			return root;
		return leftNode!=null?leftNode:rightNode;
	}
	
	/**
	 * ������������������㷨
	 * @param root
	 * @return
	 */
	public List<Integer> bfs(TreeNode root){
		List<Integer> list = new ArrayList<>();
		if(root==null)
			return list;
		Queue< TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()){
			TreeNode node = queue.remove();
			list.add(node.val);
			if(node.left!=null)
				queue.offer(node.left);
			if(node.right!=null)
				queue.offer(node.right);
		}
		return list;
	}
	
	/**
	 * �ж��Ƿ�����ȫ������
	 * @return
	 */
	public boolean isCompleteBST(TreeNode root){
		if(root==null)
			return true;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		boolean isLast = false;
		while(!queue.isEmpty()){
			TreeNode node = queue.remove();
			if(!isLast){
				if(node.left!=null || node.right!=null){
					queue.offer(node.left);
					queue.offer(node.right);
				}else if(node.left==null&&node.right!=null){
					return false;
				}else if(node.left!=null && node.right==null){
					//��δ������Ҫ�У����뽫��һ�����������
					//�Ľڵ���ӽڵ���뵽�����У��������жϣ���������©��
					queue.offer(node.left);
					isLast=true;
				}else
					isLast=true;
			}else{
				if(node.left!=null||node.right!=null)
					return false;
			}
		}
		return true;
	}
	
	/**
	 * �ж϶��������Ƿ����·���͵��ڸ���ֵ��·��
	 * 1���������������
	 * 2����sum-�����Ľڵ�ֵ��������Ҷ�ӽڵ�ʱ����sum==0���򷵻�true��
	 * 3�������������������false��
	 * @param root
	 * @param sum
	 * @return
	 */
	public boolean hasPathSum(TreeNode root, int sum) {
		if(root==null)
			return false;
		sum-=root.val;
		if(root.left==null&&root.right==null&&sum==0)
			return true;
		return hasPathSum(root.left, sum)||hasPathSum(root.right, sum);
	}

	/**
	 * �ҳ���������·���͵��ڸ���ֵ������·�����Ӹ��ڵ㵽Ҷ�ӽڵ��·��
	 * 1���������дӸ��ڵ㵽Ҷ�ӽڵ��·��
	 * 2���ж�·�����Ƿ���ڶ�ֵ
	 * @param root
	 * @param sum
	 * @return
	 */
	public List<List<Integer>> pathSumEqualNum(TreeNode root,int sum){
		List<List<Integer>>list = new ArrayList<>();
		   if(root==null)
			   return list;
		   pathHelp(root,list,sum,"");
		   return list;
	}
	private void pathHelp(TreeNode root, List<List<Integer>> list, int sum,String path) {
		if(root==null)
			return ;
		if(root.left==null&&root.right==null){
			path=path+root.val;
			String[] str = path.split("#");
			List<Integer> res = new ArrayList<>();
			for(String s:str)
				sum-=Integer.valueOf(s);
			if(sum==0){
				for(String s:str)
					res.add(Integer.valueOf(s));
				list.add(res);
			}
			return;
		}else
			path=path + root.val+"#";
		pathHelp(root.left, list, sum, path);
		pathHelp(root.right, list, sum, path);
	}
	
	/**
	 * count all the node of the compelete B tree
	 * return the num of node on the tree root
	 * 该算法结果正确，但是leetcode报TLE异常，算法有待优化
	 * @param root
	 * @return
	 */
	public int countNodes1(TreeNode root) {
		if(root==null)
			return 0;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int count = 0;
		while(!queue.isEmpty()){
			TreeNode node = queue.remove();
			count++;
			if(node.left!=null)
				queue.offer(node.left);
			if(node.right!=null)
				queue.offer(node.right);
		}
		System.out.println(queue.size());
		return count;
	}

	/**
	 * count all the node of the compelete B tree
	 * return the num of node on the tree root
	 * 222. Count Complete Tree Nodes
	 * @param root
	 * @return
	 */
	public int countNodes(TreeNode root) {
		if(root==null)
			return 0;
		int left = heightLeft(root);
		int right = heightRight(root);
		if(left==right)
			return (1<<left)-1;
		else
			return 1+countNodes(root.left)+countNodes(root.right);
	}
	private int heightRight(TreeNode right) {
		int count = 0;
		while (right!=null){
			count++;
			right=right.right;
		}
		return count;
	}
	private int heightLeft(TreeNode left) {
		int count=0;
		while(left!=null){
			count++;
			left=left.left;
		}
		return count;
	}
}
